\documentclass[12pt,a4paper]{scrreprt}
\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}%for url cites
\usepackage{listings}%source code
\usepackage{plain}
\usepackage{graphicx}
\usepackage{float}
%\usepackage{paralist}
\usepackage{pgfplots}
\usepackage{pgfplotstable}
\usepackage[colorlinks=true,linkcolor=black]{hyperref}
\setlength{\parindent}{0ex} 
\usepackage{algorithm2e}


\bibliographystyle{plain} 

\begin{document}

\thispagestyle{empty}
\begin{center}
\Large{Hochschule Karlsruhe - Technik und Wirtschaft (HsKA)}\\
\end{center}


\begin{center}
\Large{Fachbereich Informatik}
\end{center}
\begin{verbatim}


\end{verbatim}
\begin{center}
\textbf{\LARGE{Projektbericht}}
\end{center}
\begin{verbatim}

\end{verbatim}
\begin{center}
\textbf{\LARGE{Algorithmen Labor}}
\end{center}
\begin{verbatim}

\end{verbatim}
\begin{center}
\textbf{im Studiengang Informatik Master}
\end{center}
\begin{verbatim}

\end{verbatim}

\begin{flushleft}
\begin{tabular}{lll}
\textbf{Thema:} && Berechnung der konvexen Hülle \\
& & \\
& & \\
\textbf{Semester:}  && SS2013 \\
& & \\
& & \\
\textbf{eingereicht von:} & & Claudio Grau \flq{}42538\frq{}\\
& & Julia Burgard \flq{}42539\frq{}\\

\end{tabular}
\end{flushleft}

\tableofcontents

\chapter{Algorithmen} 
\section{Graham Scan}
%Quick Hull MergeHull...

Die Eingabe des Graham Scan Algorithmus ist eine zweidimensionale Punktemenge in der euklidischen Ebene, aus der die konvexe Hülle in O(n lg n) Zeit bestimmt werden kann. Im Folgenden wird der Ablauf des Algorithmus in Pseudocode beschrieben.\\\\

\begin{algorithm}[H]
 \SetAlgoLined


 \KwData{Array p mit n Punkten}
 \KwResult{Alle Punkte auf der konvexen Hülle} 
\vspace{3 mm}
Berechne den Punkt \textit{p0} mit der minimalen Y-Koordinate. Bei mehreren minimalen Y-Koordinaten wähle den Punkt mit der kleinsten X-Koordinate.\\
\vspace{2 mm}
\textit{SortedP} sei die restliche Punktemenge, welche entgegen dem Uhrzeigersinn relativ zum Punkt p0 sortiert ist.\\
\vspace{2 mm}
Erstelle einen \textit{Stack s}. \\
\vspace{2 mm}
Push \textit{p0} und die ersten zwei Punkte aus \textit{SortedP} auf den Stack.\\
\vspace{2 mm}
\For{i=2 to i< Länge von sortedP}
{
	\If{ Der Vektor (zweitoberstes Element auf s, sortedP[i]) liegt links vom Vektor ( zweitoberstes Element auf s, oberstes Element auf s) (*)\label{kreuzprodukt}} 
	{
		Push sortedP[i] auf s.\\
		i= i+1
	}
	Entferne das oberste Element von s.\\
}
\Return{s}
 \caption{Graham Scan Algorithmus}
\end{algorithm}
\vspace{10 mm}
Um zu bestimmen, ob ein bestimmter Punkt in der konvexen Hülle liegt \hyperref[kreuzprodukt]{(*)}, wird das Kreuzprodukt zweier Vektoren folgendermaßen berechnet:


\begin{center}
\vspace{5mm}
\begin{math}
Kreuzprodukt = (p2.x  - p1.x) * (p3.y - p1.y) -  (p3.x - p1.x) * (p2.y - p1.y)
\end{math}
\end{center}

\newpage


\textbf{Kreuzprodukt >0:} Der Punkt p2 liegt rechts (im Uhrzeigersinn) des Vektors(p1,p3).

\begin{figure}[htbp]
\centering
\includegraphics[width=0.3\textwidth]{Bilder/KreuzproduktGroesser0.png}
\end{figure}


\textbf{Kreuzprodukt <0:} Der Punkt p2 liegt links (entgegen dem Uhrzeigersinn) des Vektors(p1,p3) und ist somit kein Punkt auf der konvexen Hülle.


\begin{figure}[htbp]
\centering
\includegraphics[width=0.3\textwidth]{Bilder/KreuzproduktKleiner0}
\end{figure}


\textbf{Kreuzprodukt ==0:} Der Punkt p2 liegt auf dem Vektor (p1,p3).


\begin{figure}[htbp]
\centering
\includegraphics[width=0.3\textwidth]{Bilder/KreuzproduktGleich0}
\end{figure}

~\cite{SWB-326463232}

\newpage

\section{Merge Hull}

Mit dem Merge Hull Algorithmus kann die konvexe Hülle in O(n log(n)) bestimmt werden. Mit dem Divide and Conquer Verfahren wird die Punktemenge geteilt, bis die konvexe Hülle direkt bestimmt werden kann. Danach werden die konvexen Hüllen zusammengefügt. Im Folgenden wird er Algorithmus in Pseudocode beschrieben.


\vspace{3mm}
\begin{algorithm}[H]
 \SetAlgoLined
 \KwData{Sortierte Punktemenge \textit{p}}
 \KwResult{Alle Punkte auf der konvexen Hülle \textit{K}} 
\vspace{3 mm}
berechneKonvexeHuelle (\textit{Punkte p})\\
\vspace{2 mm}
\eIf {Anzahl von \textit{p} <= 2}
{
Konstruiere die konvexe Hülle \textit{KGesamt} aus \textit{p} direkt.
}
{
Teile die Punktemenge \textit{p} in zwei Hälften \textit{pLinks} und \textit{pRechts} anhand ihrer x Werte. \\
\vspace{1 mm}
\textit{KLinks}= berechneKonvexeHuelle(\textit{pLeft})\\
\textit{KRight}= berechneKonvexeHuelle(\textit{pRight})\\
\vspace{1 mm}
obereGrenzen= sucheObereGrenze(\textit{KLeft}, \textit{KRight}) (*) \\
untereGrenzen= sucheUntereGrenze(\textit{KLeft}, \textit{KRight}) (*)\\
KGesamt = Füge KLeft und KRight anhand der oberen und unteren Grenze zusammen
}
\Return{KGesamt}
\vspace{3 mm}
 \caption{Merge Hull Algorithmus}
\label{divConqAlgo}
\end{algorithm}
\vspace{3mm}
Die oberen und unteren Grenzen (*) des Algorithmus werden folgendermaßen gesucht:
\newpage


\begin{algorithm}[H]
 \SetAlgoLined
 \KwData{Zwei konvexe Hüllen \textit{KLeft} und \textit{KRight} }
 \KwResult{Oberen Grenzen der konvexen Hüllen} 
\vspace{3 mm}
sucheObereGrenzen (\textit{KLeft}, \textit{KRight})\\
\vspace{2 mm}

pointLeft =  Suche den Punkt mit der größten x Koordinate\\
point Right = Suche den Punkt mit der kleinsten x Koordinate\\

\Repeat{pointLeft und pointRight haben sich geändert} 
{
	nextPointLeft = Nächster Punkt entgegen dem Uhrzeigersinn von KLeft\\
	nextPointRight = Nächster Punkt im Uhrzeigersinn von KRight\\
	\vspace{1 mm}
	\While{Vetor(pointRight, nextPointLeft) liegt rechts vom Vektor(pointRight, pointLeft)}{
		pointLeft=nextPointLeft\\
		nextPointLeft = Nächster Punkt entgegen dem Uhrzeigersinn von KLeft
	}
	\vspace{1 mm}
	\While{Vetor(pointLeft, nextPointRight) liegt links vom Vektor(pointLeft, pointRight)}{
		pointRight=nextPointRight\\
		nextPointRight = Nächster Punkt im Uhrzeigersinn von KRight
	}

}
\Return{nextPointLeft und nextPointRight}
\vspace{3 mm}
 \caption{Suche die oberen Grenzen der konvexen Hüllen}
\label{divConqAlgo}
\end{algorithm}
\vspace{5 mm}
 \newpage
Die Unteren Grenzen werden fast analog dazu gesucht:
\\\\
\begin{algorithm}[H]
 \SetAlgoLined
 \KwData{Zwei konvexe Hüllen \textit{KLeft} und \textit{KRight} }
 \KwResult{Unteren Grenzen der konvexen Hüllen} 
\vspace{3 mm}
sucheUntereGrenzen (\textit{KLeft}, \textit{KRight})\\
\vspace{2 mm}

pointLeft =  Suche den Punkt mit der größten x Koordinate\\
point Right = Suche den Punkt mit der kleinsten x Koordinate\\

\Repeat{pointLeft und pointRight haben sich geändert} 
{
	nextPointLeft = Nächster Punkt im Uhrzeigersinn von KLeft\\
	nextPointRight = Nächster Punkt entgegen dem Uhrzeigersinn von KRight\\
	\vspace{1 mm}
	\While{Vetor(pointRight, nextPointLeft) liegt links vom Vektor(pointRight, pointLeft)}{
		pointLeft=nextPointLeft\\
		nextPointLeft = Nächster Punkt im Uhrzeigersinn von KLeft\\
	}
	\vspace{1 mm}
	\While{Vetor(pointLeft, nextPointRight) liegt rechts vom Vektor(pointLeft, pointRight)}{
		pointRight=nextPointRight\\
		nextPointRight = Nächster Punkt entgegen dem Uhrzeigersinn von KRight\\
	}

}
\Return{nextPointLeft und nextPointRight}
\vspace{3 mm}
 \caption{Suche die unteren Grenzen der konvexen Hüllen}
\label{divConqAlgo}
\end{algorithm}
\vspace{5 mm}



\section{Quick Hull}

Per Quick Hull kann die konvexe Hülle im Mittel in O(n log(n)) bestimmt werden. Allerdings im ungünstigen Fall auch O(n$^{2}$). Die Punkte werden anhand einer Geraden geteilt. Alle rechts der Gerade liegenden Punkte werden betrachtet, um den weitestentfernten Punkt zu bestimmen.
Das selbe wird wiederholt, mit dem Anfang der ursprünglichen gerade und dem weitestentfernten Punkt sowie mit dem Ende der ursprünglichen Geraden und dem weitestentfernten Punkt. So lange, bis keine Punkte rechts der Gerade mehr liegen.
Im Folgenden wird er Algorithmus in Pseudocode beschrieben.


\vspace{3mm}
\begin{algorithm}[H]
 \SetAlgoLined
 \floatname{algorithm}{ddddd}
 \KwData{Zwei konvexe Hüllen \textit{KLeft} und \textit{KRight} }
 \KwResult{Unteren Grenzen der konvexen Hüllen} 
\vspace{3 mm}
    ConvexHull := \{\}\\
    A := Find left most point\\
    B := Find right most point\\

	\vspace{3 mm}
    
    segmentLeft  := points in S that are on the right side of the oriented line from A to B\\    
    segmentRight := points in S that are on the right side of the oriented line from B to A\\

    \vspace{3 mm}

    Add A to ConvexHull\\
    FindHull (S1, A, B) \\
    Add B to ConvexHull\\
    FindHull (S2, B, A)\\

\vspace{3 mm}
 \caption{Quick-Hull Algorithmus}
\end{algorithm}
\vspace{5 mm}

\vspace{3mm}
Es folgt die verwendete Methode \textit{findHull()}:
\newpage


\begin{algorithm}[H]
 \SetAlgoLined
 \KwData{List of points \textit{S}, Start Point of line \textit{A} and end Point of line \textit{B}}
 \KwResult{Adds farest point of \textit{S} to \textit{ConvexHull}}
\vspace{3 mm}
\If{\textit{List} empty} 
{
\Return 
}

\vspace{3 mm}

farestPoint := get point from \textit{S} which has the maximum distance to line from \textit{A} to \textit{B}

\vspace{3 mm}

    segmentLeft  := points in S which are right of line from \textit{A} to \textit{farestPoint}\\
    segmentRight := points in S which are right of line from \textit{farestPoint} to \textit{B}\\
    
    \vspace{3 mm}
    
    \textit{findHull}(\textit{segmentLeft}, \textit{A}, \textit{farestPoint})\\
    
    \vspace{3 mm}
    
    ConvexHull := ConvexHull $\cup$ farestPoint
    
    \vspace{3 mm}        
        
    \textit{findHull}(\textit{segmentRight}, \textit{farestPoint}, \textit{B})\\
    
\vspace{3 mm}
 \caption{Find-Hull Teil-Algorithmus}
\end{algorithm}

\chapter{Implementierung} 
\section{Klassendiagramme}
\subsection{GrahamScan Implementierung}

\begin{figure}[htbp]
\centering
\includegraphics[width=0.8\textwidth]{Bilder/Klassendiagramm}
\end{figure}

\newpage

\subsection{Model und Viewer}

\begin{figure}[htbp]
\centering
\includegraphics[width=1.0\textwidth]{Bilder/Klassendiagramm2}
\end{figure}
\newpage

\subsection{Tests und Zeitmessung}

\begin{figure}[htbp]
\centering
\includegraphics[width=1.0\textwidth]{Bilder/Klassendiagramm3}
\end{figure}

\newpage
\subsection{MergeHull Implementierung}

\begin{figure}[htbp]
\centering
\includegraphics[width=0.8\textwidth]{Bilder/Klassendiagramm4.png}
\end{figure}

\newpage
\subsection{QuickHull Implementierung}

\begin{figure}[htbp]
\centering
\includegraphics[width=0.8\textwidth]{Bilder/Klassendiagramm5.png}
\end{figure}

\chapter{Zeitmessung} 
\section{GrahamScan: Zufallszahlen}
\begin{tikzpicture}
		\begin{axis}[width=1\textwidth,height=0.43\textheight,
			title={GrahamScan: Punkte sind zufällig in der Ebene verteilt}]

		\addplot table {Zeitmessungen/randomPointsTimeMeasurementGrahamScan.csv};
		\end{axis}
\end{tikzpicture}






\begin{center}
\pgfplotstabletypeset[
    col sep=tab,
    string type,
    columns/AnzahlPunkte/.style={column name=Anzahl der Punkte, column type={|l}},
    columns/Zeit/.style={column name=Zeit in ms, column type={|l|}},
    every head row/.style={before row=\hline,after row=\hline},
    every last row/.style={after row=\hline},
    ]{Zeitmessungen/randomPointsTimeMeasurementGrahamScan.csv}
\end{center}

\newpage
\section{GrahamScan: Alle Punkte liegen auf einem Kreis}
\begin{tikzpicture}
	\begin{axis}[width=1\textwidth,height=0.463\textheight,
			title={GrahamScan: Punkte befinden sich in einem Kreis}]
		\addplot table {Zeitmessungen/pointsInACircleTimeMeasurementGrahamScan.csv};
	\end{axis}
\end{tikzpicture}

\begin{center}
\pgfplotstabletypeset[
    col sep=tab,
    string type,
    columns/AnzahlPunkte/.style={column name=Anzahl der Punkte, column type={|l}},
    columns/Zeit/.style={column name=Zeit in ms, column type={|l|}},
    every head row/.style={before row=\hline,after row=\hline},
    every last row/.style={after row=\hline},
    ]{Zeitmessungen/pointsInACircleTimeMeasurementGrahamScan.csv}
\end{center}

\section{MergeHull: Zufallszahlen}

\begin{tikzpicture}
		\begin{axis}[width=1\textwidth,height=0.43\textheight,
			title={MergeHull: Punkte sind zufällig in der Ebene verteilt}]

		\addplot table {Zeitmessungen/randomPointsTimeMeasurementMergeHull.csv};
		\end{axis}
\end{tikzpicture}

\begin{center}
\pgfplotstabletypeset[
    col sep=tab,
    string type,
    columns/AnzahlPunkte/.style={column name=Anzahl der Punkte, column type={|l}},
    columns/Zeit/.style={column name=Zeit in ms, column type={|l|}},
    every head row/.style={before row=\hline,after row=\hline},
    every last row/.style={after row=\hline},
    ]{Zeitmessungen/randomPointsTimeMeasurementMergeHull.csv}
\end{center}

\newpage
\section{MergeHull: Alle Punkte liegen auf einem Kreis}
\begin{tikzpicture}
	\begin{axis}[width=1\textwidth,height=0.463\textheight,
			title={MergeHull: Punkte befinden sich in einem Kreis}]
		\addplot table {Zeitmessungen/pointsInACircleTimeMeasurementMergeHull.csv};
	\end{axis}
\end{tikzpicture}

\begin{center}
\pgfplotstabletypeset[
    col sep=tab,
    string type,
    columns/AnzahlPunkte/.style={column name=Anzahl der Punkte, column type={|l}},
    columns/Zeit/.style={column name=Zeit in ms, column type={|l|}},
    every head row/.style={before row=\hline,after row=\hline},
    every last row/.style={after row=\hline},
    ]{Zeitmessungen/pointsInACircleTimeMeasurementMergeHull.csv}
\end{center}


\section{QuickHull: Zufallszahlen}

\begin{tikzpicture}
		\begin{axis}[width=1\textwidth,height=0.43\textheight,
			title={QuickHull: Punkte sind zufällig in der Ebene verteilt}]

		\addplot table {Zeitmessungen/randomPointsTimeMeasurementQuickHull.csv};
		\end{axis}
\end{tikzpicture}

\begin{center}
\pgfplotstabletypeset[
    col sep=tab,
    string type,
    columns/AnzahlPunkte/.style={column name=Anzahl der Punkte, column type={|l}},
    columns/Zeit/.style={column name=Zeit in ms, column type={|l|}},
    every head row/.style={before row=\hline,after row=\hline},
    every last row/.style={after row=\hline},
    ]{Zeitmessungen/randomPointsTimeMeasurementQuickHull.csv}
\end{center}

\newpage
\section{QuickHull: Alle Punkte liegen auf einem Kreis}
\begin{tikzpicture}
	\begin{axis}[width=1\textwidth,height=0.463\textheight,
			title={QuickHull: Punkte befinden sich in einem Kreis}]
		\addplot table {Zeitmessungen/pointsInACircleTimeMeasurementQuickHull.csv};
	\end{axis}
\end{tikzpicture}

\begin{center}
\pgfplotstabletypeset[
    col sep=tab,
    string type,
    columns/AnzahlPunkte/.style={column name=Anzahl der Punkte, column type={|l}},
    columns/Zeit/.style={column name=Zeit in ms, column type={|l|}},
    every head row/.style={before row=\hline,after row=\hline},
    every last row/.style={after row=\hline},
    ]{Zeitmessungen/pointsInACircleTimeMeasurementQuickHull.csv}
\end{center}

%\bibliography{literatur}


\end{document}